# 狄克斯特拉算法的使用demo与分析；
# 广度优先搜素（BFS）的应用主要在于寻找最短路径，这种算法的应用主要用于一个无权的图中进行搜索
# 或者说图中的每个节点的权重都是相同的；

# 而狄克斯特拉算法主要用用于加权图的计算，但是要注意，这种计算需要图的限制为：
# 1. 单向加权图（不能有环）
# 2. 不能有负权重的存在（这主要由于更新策略的缘故，每个节点只进行更新一次




# 一个具体的例子见README中

graph = dict()

graph["A"] = dict()
graph["A"]["B"] = 5
graph["A"]["C"] = 2

graph["B"] = dict()
graph["B"]["D"] = 4
graph["B"]["E"] = 2

graph["C"] = dict()
graph["C"]["B"] = 8
graph["C"]["E"] = 7

graph["D"] = dict()
graph["D"]["E"] = 6
graph["D"]["F"] = 3

graph["E"] = dict()
graph["E"]["F"] = 1

graph["F"] = dict()
graph["F"] = {}         #终点没有任何的邻居

processed = []          #队列表示已经处理过

infinity = float("inf")
costs = dict()
costs["B"] = 5
costs["C"] = 2
costs["D"] = infinity
costs["E"] = infinity
costs["F"] = infinity   #从起点看，只能获取直接到达的节点的花费，无法直接到达的标记为 infinity（无穷大）

parents = dict()
parents["A"] = None
parents["B"] = "A"
parents["C"] = "A"
parents["D"] = None
parents["E"] = None
parents["F"] = None     #字典用于记录父节点

def find_lowest_cost_node(costs):
    lowest_cost = infinity
    lowest_cost_node = None
    for node in costs:
        cost = costs[node]
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node

def find_shortest_path(graph, dest):
    node = find_lowest_cost_node(costs)
    while node is not None:
        neighbors = graph[node].keys()
        for nei_node in neighbors:
            if costs[nei_node] > costs[node] + graph[node][nei_node]:
                costs[nei_node] = costs[node] + graph[node][nei_node]
                parents[nei_node] = node
        processed.append(node)
        node = find_lowest_cost_node(costs)
    return costs[dest]

des = "F"
res = find_shortest_path(graph, des)
print("the shortest path to dest is", res)
par = parents[des]
while par is not None:
    print(par)
    par = parents[par]